import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution400 {

    static List<Long> searchArr = new ArrayList<>();

    static {
        long res = 0, count = 9;
        searchArr.add(res);
        for(int i = 1; res < Integer.MAX_VALUE; i++, count *= 10){
            res = res + (count * i);
            searchArr.add(res);
        }
    }

    private int getStartInd(int n){
        int left = 0, right = searchArr.size() - 1;
        while(left <= right){
            int mid = left + ((right - left) / 2);
            long midNum = searchArr.get(mid);
            if(midNum == n){
                return mid;
            }
            else if(midNum < n){
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }
        }
        return right;
    }

    private int getStartNum(int startInd){
        int res = 0;
        for (int i = 0; i < startInd; i++) {
            res = res * 10 + 9;
        }
        return res;
    }

    private int getBitCount(int num){
        return (int)Math.log10(num) + 1;
    }

    private int getLocNum(int loc, int num){
        List<Integer> deque = new LinkedList<>();
        for (; num > 0; num /= 10) {
            deque.add(0, num % 10);
        }
        return deque.get(loc);
    }

    public int findNthDigit(int n) {
        int startInd = getStartInd(n);
        n -= searchArr.get(startInd);
        if(n == 0){return startInd == 0 ? 0 : 9;}
        int startNum = getStartNum(startInd);
        int bitCount = getBitCount(startNum + 1);
        int loc = n % bitCount;
        int tmpNum = startNum + (n / bitCount);
        if(loc == 0){loc = bitCount;}
        else{tmpNum++;}
        return getLocNum(loc - 1, tmpNum);
    }

    public static void main(String[] args) {
        Solution400 s = new Solution400();
        s.findNthDigit(11);
    }
}
